function maxSubArray(nums: number[]): number {
  // dp, 当前连续值最大值
  const dp: number[] = [];
  // 状态改变控制, 要不是我自己，要不就是跟上个连续的最大值进行相加，比较它们
  // dp[i] = max(dp[i], dp[i-1]+dp[i])

  // 初始值
  dp[0] = nums[0];


  // 循环修改状态
  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(nums[i], dp[i-1]+nums[i])
  }  

  // 找到下标连续值最大的
  return Math.max(...dp);
}

console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]));
console.log(maxSubArray([1]));
console.log(maxSubArray([5,4,-1,7,8]));
